package com.leetcode.algorithm.y22.m07.w4;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 113. 路径总和 II
 * 
 * https://leetcode.cn/problems/path-sum-ii/
 * 
 * @author jie.deng
 *
 */
class Question0113Solution03 {

	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		List<List<Integer>> retList = new ArrayList<>();
		if (root == null) {
			return retList;
		}
		Deque<Integer> pathDeQueue = new ArrayDeque<>();
		dfs(root, targetSum, pathDeQueue, retList);
		return retList;
	}

	private void dfs(TreeNode cur, int targetSum, Deque<Integer> pathQueue, List<List<Integer>> list) {
		// 先序遍历
		// 当前层
		targetSum -= cur.val;
		pathQueue.offerLast(cur.val);

		if (cur.left == null && cur.right == null) {
			// 递归终止条件
			if (targetSum == 0) {
				list.add(new ArrayList<>(pathQueue));
			}
		} else {
			// 递归调用
			if (cur.left != null) {
				dfs(cur.left, targetSum, pathQueue, list);
			}
			if (cur.right != null) {
				dfs(cur.right, targetSum, pathQueue, list);
			}
		}

		// 回溯
		pathQueue.pollLast();
	}

}